<template>
    <div class="demo-collapse">
        <el-collapse v-model="activeNames" @change="handleChange">
            <el-collapse-item title="解题思路" name="thinking">
                <div>
                    <div>
                        定义n×n的方阵序列D-1, D0 , … Dn－1,
                    </div>
                    <div>
                        初始化： D-1＝C<br>
                        &nbsp;&nbsp;D-1[i][j]＝边&lt;i,j>的长度，表示初始的从i到j的最短路径长度，即它是从i到j的中间不经过其他中间点的最短路径。
                    </div>
                    <div>
                        迭代：设Dk-1已求出，如何得到Dk（0≤k≤n-1）？
                    </div>
                    <div>
                        <ul>
                            <li>&nbsp;&nbsp;Dk-1[i][j]表示从i到j的中间点不大于k-1的最短路径p：i…j，</li>
                            <li>&nbsp;&nbsp;考虑将顶点k加入路径p得到顶点序列q：i…k…j，</li>
                            <li>&nbsp;&nbsp;若q不是路径，则当前的最短路径仍是上一步结果：Dk[i][j]= Dk－1[i][j]；</li>
                            <li>&nbsp;&nbsp;否则若q的长度小于p的长度，则用q取代p作为从i到j的最短路径</li>
                        </ul>
                    </div>
                    <div>
                        因为q的两条子路径i…k和k…j皆是中间点不大于k－1的最短路径，所以从i到j中间点不大于k的最短路径长度为：
                        Dk[i][j]＝min{ Dk-1[i][j], Dk-1[i][k] +Dk-1[k][j] }
                    </div>
                </div>
            </el-collapse-item>
            <el-collapse-item title="代码实现" name="code">
                <!-- <el-image style="width:100%" :src="url" :fit="fit" loading="lazy"></el-image> -->
                <div v-highlight>
                    <div>C/C++:</div>
                    <pre class="language-javascript">
                      <code>
                        #include&lt;iostream>
                            using namespace std;
                            
                            const int N = 210,M = 20010,INF = 0x3f3f3f3f;
                            int n,m,Q;
                            int d[N][N]; // d[i][j] 表示从i到j的距离
                            
                            void floyd(){
                                for(int k = 1; k &lt;= n; k ++)
                                    for(int i = 1; i &lt;= n; i ++)
                                        for(int j = 1; j &lt;= n; j ++)
                                            d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
                            }
                            
                            int main(){
                                scanf("%d%d%d",&n,&m,&Q);
                                
                                // 初始化
                                for(int i = 1; i &lt;= n; i ++)
                                    for(int j = 1; j &lt;= n; j ++){
                                        if(i == j) d[i][j] = 0;
                                        else d[i][j] = INF;
                                    }
                                
                                // 加边
                                while(m --){
                                    int a,b,c;
                                    scanf("%d%d%d",&a,&b,&c);
                                    
                                    d[a][b] = min(d[a][b],c); // 两点之间如果有多条边，那么选最短的边即可
                                }
                                
                                // floyd
                                floyd();
                                
                                // 处理询问
                                while(Q --){
                                    int a,b;
                                    scanf("%d%d",&a,&b);
                                    
                                    if(d[a][b] > INF / 2) puts("impossible"); // 边权可能有负数，所以不会直接等于INF
                                    else printf("%d\n",d[a][b]);
                                }
                                
                                return 0;
                            }
                            
                      </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Python:</div>
                    <pre class="language-javascript">
                        <code>
                            # 输入距离矩阵，-1表示初始化时两点不可达
                            matrix = [[0, 50, -1, 40, 25, 10],
                                    [50, 0, 15, 20, -1, 25],
                                    [-1, 15, 0, 10, 20, -1],
                                    [40, 20, 10, 0, 10, 25],
                                    [25, -1, 20, 10, 0, 55],
                                    [10, 25, -1, 25, 55, 0]]
 
 
                            def floyd(W):
                                # 首先获取节点数
                                node_number = len(W)
 
                                # 初始化路由矩阵 n x n
                                R = [[0 for i in range(node_number)] for j in range(node_number)]
                                for i in range(node_number):
                                    for j in range(node_number):
                                        if W[i][j] > 0: # 如果 i+1 与 j+1 两点之间可达
                                            R[i][j] = j+1 # 那么记录 i+1 --> j+1 路由的终点
                                        else:           # 如果 两点间不可达
                                            R[i][j] = 0 # 则记录点为0
                                # 查看初始化的路由矩阵
                                for row in R:
                                    print(row)
 
                                # 循环求W_n和R_n
                                for k in range(node_number): # 对每个点都作为中转节点更新距离和路由矩阵
                                    for i in range(node_number): # 遍历每个点
                                        for j in range(node_number): 
                                            if W[i][k] > 0 and W[k][j] > 0 and (W[i][k] + W[k][j] &lt; W[i][j] or W[i][j] == -1):
                                                W[i][j] = W[i][k] + W[k][j] 
                                                R[i][j] = k+1
                                    print("第%d次循环:" % (k+1))
                                    print("距离矩阵:")
                                    for row in W:
                                        print(row)
                                    print("路由矩阵:")
                                    for row in R:
                                        print(row)
 
                                #打印路径
                                for i in range(node_number):
                                    for j in range(node_number):
                                        if R[i][j] != j+1 and R[i][j] != 0:
                                            print(f'{i+1}--{R[i][j]}--{j+1}：{W[i][j]}')
                                        elif R[i][j] == j+1:
                                            print(f'{i+1}--{j+1}：{W[i][j]}')
 
 
                            floyd(matrix)
 
                        </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Java:</div>
                    <pre class="language-javascript">
                      <code>
                        package com.haiyang.algorithm.floyd;

                        import com.sun.corba.se.impl.orbutil.graph.Graph;

                        import java.util.Arrays;

                        /**
                        * @author haiYang
                        * @create 2022-02-09 10:44
                        */
                        public class FloydAlgorithm {
                            public static void main(String[] args) {
                                // 测试看看图是否创建成功
                                char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
                                //创建邻接矩阵
                                int[][] matrix = new int[vertex.length][vertex.length];
                                final int N = 65535;
                                matrix[0] = new int[]{0, 5, 7, N, N, N, 2};
                                matrix[1] = new int[]{5, 0, N, 9, N, N, 3};
                                matrix[2] = new int[]{7, N, 0, N, 8, N, N};
                                matrix[3] = new int[]{N, 9, N, 0, N, 4, N};
                                matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};
                                matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};
                                matrix[6] = new int[]{2, 3, N, N, 4, 6, 0};

                                //创建 Graph 对象
                                FGraph graph = new FGraph(vertex.length, matrix, vertex);
                                //调用弗洛伊德算法
                                graph.floyd();
                                graph.show();
                                graph.showAToB('C', 'D', vertex);
                            }
                        }

                        class FGraph {
                            //顶点集合
                            private char[] vertex;
                            //邻接矩阵
                            private int[][] arcs;
                            //前驱矩阵
                            private int[][] path;

                            public FGraph(int vertexNum, int[][] arcs, char[] vertex) {
                                this.vertex = vertex;
                                this.arcs = arcs;
                                this.path = new int[vertexNum][vertexNum];
                                for (int i = 0; i &lt; vertexNum; i++) {
                                    Arrays.fill(path[i], i);
                                }
                            }

                            public void show() {
                                System.out.println("==========邻接矩阵==========");
                                for (int i = 0; i &lt; arcs.length; i++) {
                                    for (int j = 0; j &lt; arcs.length; j++) {
                                        System.out.print(arcs[i][j] + " ");
                                    }
                                    System.out.println();
                                }
                                System.out.println("==========前驱矩阵==========");
                                for (int i = 0; i &lt; path.length; i++) {
                                    for (int j = 0; j &lt; path.length; j++) {
                                        System.out.print(vertex[path[i][j]] + " ");
                                    }
                                    System.out.println();
                                }
                            }

                            public void floyd() {
                                //保存距离
                                int len = 0;
                                //k为中间顶点
                                for (int k = 0; k &lt; arcs.length; k++) {
                                    //i为开始顶点
                                    for (int i = 0; i &lt; arcs.length; i++) {
                                        //j为结束顶点
                                        for (int j = 0; j &lt; arcs.length; j++) {
                                            len = arcs[i][k] + arcs[k][j];
                                            if (len &lt; arcs[i][j]) {
                                                arcs[i][j] = len;//更新距离
                                                path[i][j] = path[k][j];//更新前驱矩阵
                                            }
                                        }
                                    }
                                }

                            }

                            public void showAToB(char a, char b, char[] vertex) {
                                int beginIndex = 0;
                                int endIndex = 0;
                                for (int i = 0; i &lt; vertex.length; i++) {
                                    if (a == vertex[i]) {
                                        beginIndex = i;
                                    }
                                    if (b == vertex[i]) {
                                        endIndex = i;
                                    }
                                }
                                System.out.println(a + "到" + b + "的距离为：" + arcs[beginIndex][endIndex]);
                                System.out.print("路径为：");
                                showAToBPath(beginIndex, endIndex, vertex);
                                System.out.print(b);
                            }

                            public void showAToBPath(int beginIndex, int endIndex, char[] vertex) {
                                if (path[beginIndex][endIndex] == endIndex && path[beginIndex][endIndex] == beginIndex) {
                                    return;
                                }
                                showAToBPath(beginIndex, path[beginIndex][endIndex], vertex);
                                System.out.print(vertex[path[beginIndex][endIndex]] + " ");

                            }

                        }

                      </code>
                    </pre>
                </div>
            </el-collapse-item>
        </el-collapse>
    </div>
</template>

<script lang="ts" setup>
import { ref } from 'vue'
const activeNames = ref(['thinking'])
const handleChange = (val: string[]) => {
    console.log(val)
}
// 代码实现部分
import "vue-code-highlight/themes/prism-solarizedlight.css";
import "vue-code-highlight/themes/window.css";

</script>
